package _0_6_回文子串_子序列_编辑距离

/*
原题链接:
https://leetcode.cn/problems/is-subsequence/

392. 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：
如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，
你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false

思路:
一. 确定dp数组以及下标含义

	dp[i][j]: 以下标i-1为结尾的字符串s, 和以下标j-1为结尾的字符串t, 相同子序列的长度为dp[i][j]

二. 确定递推公式, 考虑两种操作,
  - if(s[i-1] == t[j-1]) t中找到了一个字符在s中也出现了
    if(s[i-1] == t[j-1], 那么dp[i][j] = dp[i-1][j-1] + 1;
    因为找到了一个相同的字符, 相同子序列长度自然要在dp[i-1][j-1]的基础上加1
  - if(s[i-1] != t[j-1]) 相当于t要删除元素, 继续匹配
    if(s[i-1] != t[j-1], 此时相当于t要删除元素, t如果把当前元素t[j-1]删除, 那么dp[i][j]的数值就是
    看s[i-1]与[j-2]的比较结果了, 即: dp[i][j] = dp[i][j-1]

三. 初始化

	从递推公式可以看出dp[i][j]都是依赖于dp[i-1][j-1]和dp[i][j-1], 所以dp[0][0]和dp[i][0]是一定要初始化的
	第一行和第一列都要初始化为0

四. 确定遍历顺序

	同理从递推公式可得dp[i][j]都是依赖于dp[i-1][j-1]和dp[i][j-1],
	那么遍历顺序也应该是从上到下, 从左到右

五. 打印dp数组
*/
func isSubsequence(s string, t string) bool {

	//1.声明二维数组
	dp := make([][]int, len(s)+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, len(t)+1)
	}

	//2.填充二维数组
	for i := 1; i < len(dp); i++ {
		for j := 1; j < len(dp[i]); j++ {
			if s[i-1] == t[j-1] { //如果当前两个字符相同, 子序列长度+1, 共同比较前一位
				dp[i][j] = dp[i-1][j-1] + 1
			} else { //如果当前字符不相同, 直接比较j-1位置是否相同
				dp[i][j] = dp[i][j-1]
			}
		}
	}

	//3.返回两个字符串的公共子序列长度, 是否和s长度相同
	return dp[len(s)][len(t)] == len(s)
}
